package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/delete-node-in-a-bst/
 *  二叉树删节点 递归
 * author: hongchen.liao
 * date:  2022/8/8
 */
public class _450_Delete_Node_in_a_BST {


      //Definition for a binary tree node.
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if(root == null){
                return root;
            }
            if(root.val == key){
                if(root.left == null) return root.right;
                if(root.right == null) return root.left;
                TreeNode min = getMin(root.right);
                root.val = min.val;
                root.right = deleteNode(root.right, min.val);
            }
            if(root.val > key){
                root.left = deleteNode(root.left, key);
            }
            if(root.val < key){
                root.right = deleteNode(root.right, key);
            }
            return root;
        }

        TreeNode getMin(TreeNode root){
            while(root.left != null){
                root = root.left;
            }
            return root;
        }
    }


}
